package leetcode;

import java.util.HashMap;

public class FrogJump {

	public static void main(String[] args) {
		FrogJump object = new FrogJump();
		int[] stones = {0,1,3,5,6,8,12,17};
		object.canCross(stones);
	}
	
    public boolean canCross(int[] stones) {
        if(stones == null || stones.length <= 1){
        	return true;
        }
        //初始只能跳一步
        if(stones[1] != 1){
        	return false;
        }else if(stones.length == 2){
        	return true;
        }
        //映射着值到下标
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < stones.length; i++) {
			map.put(stones[i], i);
		}
        
        //m represent the count of stones
        int m = stones.length;
        
        //dp[i][j] : in the ith stone and last jump steps is j is real;
        //j is 1 ~ m - 1
        boolean[][] dp = new boolean[m][m];
        //dp[0][0] = true;
        dp[1][1] = true;
        for(int i = 1; i < m; i++){
        	for(int j = 1; j < m; j++){
        		if(!dp[i][j]){
        			continue;
        		}
        		//next option is j - 1, j, j + 1
        		int k = Math.max(1, j - 1);
        		for(; k <= j + 1; k++){
        			int nextStep = stones[i] + k;
        			Integer index = null;
        			if((index = map.get(nextStep)) != null ){
        				if(index == m - 1){
        					return true;
        				}
        				dp[index][k] = true;
        			}
        		}
        	}
        }
//        for (int i = 0; i < dp.length; i++) {
//        	for (int j = 0; j < m; j++) {
//        		System.out.print(dp[i][j] + "  ");
//        	}
//        	System.out.println();
//		}
        return false;
    }
}
